GATE PYQ

Process Synchronization

Q31.
A certain computation generates two arrays a and b such that a[i]=f(i)for o\leq i \lt n and b[i] = g (a[i] )for o\leq i \lt n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below. Which one of the following represents the CORRECT implementations of ExitX and EntryY?

Q32.
Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned. Which one of the following statements describes the properties achieved?

Q33.
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

Q34.
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available. AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1; } ReleaseLock(L){ L = 0; } This implementation

Q35.
The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows: P(s) : s = s - 1; if (s < 0) then wait; V(s) : s = s + 1; if (s <= 0) then wakeup a process waiting on s; Assume that P_{b} and V_{b} the wait and signal operations on binary semaphores are provided. Two binary semaphores x_{b} and y_{b} are used to implement the semaphore operations P(s) and V(s) as follows: P(s) : Pb(xb); s = s - 1; if (s < 0) { Vb(xb) ; Pb(Yb) ; } else Vb(xb); V(s) : Pb(xb) ; s = s + 1; if (s <= 0) Vb(Yb) ; Vb(xb) ; The initial values of xb and yb are respectively

Q36.
The atomic feth-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x . Consider the following implementation of P and V functions on a binary semaphore S. void P(binary_semaphoreS){ unsigned y; unsignedx =& (S->value); do { fetch-and-set x,y; } while(y); } void V (binary_semphore*S){ S_>value = 0; } Which one of the following is true?

Q37.
The wait and signal operations of a monitor are implemented using semaphores as follows. In the following, x is a condition variable, mutex is a semaphore initialized to 1, x_sem is a semaphore initialized to 0, x_count is the number of processes waiting on semaphore x_sem, initially 0, next is a semaphore initialized to 0, next_count is the number of processes waiting on semaphore next, initially 0. The body of each procedure that is visible outside the monitor is replaced with the following: P(mutex); ... body of procedure ... if (next_count > 0) V(next); else V(mutex); Each occurrence of x.wait is replaced with the following: x_count = x_count + 1; if (next_count > 0) V(next); else V(mutex); ------------------------------------------------------------ E1; x_count = x_count - 1; Each occurrence of x.signal is replaced with the following: if (x_count > 0) { next_count = next_count + 1; ------------------- E2; P(next); next_count = next_count - 1; } For correct implementation of the monitor, statements E1 and E2 are, respectively,

Q38.
The semaphore variables full, empty and mutex are initialized to 0, n and 1, respectively. Process P1 repeatedly adds one item at a time to a buffer of size n, and process P2 repeatedly removes one item at a time from the same buffer using the programs given below. In the programs, K, L, M and N are unspecified statements. P1 while (1) { K; P(mutex); Add an item to the buffer; V(mutex); L; } P2 while (1) { M; P(mutex); Remove an item from the buffer; V(mutex); N; } The statements K, L, M and N are respectively

Q39.
Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and R4, as shown below. \begin{array}{|l|l|}\hline \textbf{P1} & \textbf{P2} \\ \text{Compute: } & \text{Compute;} \\ \text{Use $R1;$ } & \text{Use $R1;$} \\ \text{Use $R2;$ } & \text{Use $R2;$}\\ \text{Use $R3;$ } & \text{Use $R3;$} \\ \text{Use $R4;$ } & \text{Use $R4;$} \\\hline \end{array} Both processes are started at the same time, and each resource can be accessed by only one process at a time The following scheduling constraints exist between the access of resources by the processes: P2 must complete use of R1 before P1 gets access to R1. P1 must complete use of R2 before P2 gets access to R2. P2 must complete use of R3 before P1 gets access to R3. P1 must complete use of R4 before P2 gets access to R4. There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?

Q40.
Given below is a program which when executed spawns two concurrent processes : semaphore X : = 0 ; /* Process now forks into concurrent processes P1 & P2 */ \begin{array}{|l|l|}\hline \text{$P1$} & \text{$P2$} \\\hline \text{repeat forever } & \text{repeat forever} \\ \text{$V (X) ;$ } & \text{$ P(X) ;$} \\ \text{Compute; } & \text{Compute;}\\ \text{$P(X) ;$ } & \text{$V(X) ;$} \\\hline \end{array} Consider the following statements about processes P1 and P2: I.It is possible for process P1 to starve. II.It is possible for process P2 to starve. Which of the following holds?